Prior Art.
Many areas of engineering and physics require taking a computer representation of a two-dimensional or three-dimensional object, dividing the representation into pieces and storing the pieces. The division is aimed at providing easier storage, transmission or manipulation of the representation. Examples of fields in which such division is important include (i) the field of mesh generation which arises in computational physics and computer aided design, and (ii) the field of communications where image storage, transmission and representation is fundamental.
In the prior art there are many techniques for subdividing and storing a computer representation of an object. Perhaps the most commonly used methods are the quadtree and octree division methods. The quadtree method applies to representations of two-dimensional objects. The octree method applies to representations of three-dimensional objects. A basic reference describing the quadtree method is M. A. Yerry and M. S. Shepard, A Modified Quadtree Approach to Finite Element Mesh Generation, 3 IEEE Computer Graphics and Applications 39 (January/February 1983). Both the quadtree and octree division methods are achieved by the use of simple recursive algorithms that isotropically divide the representation into pieces. In many actual applications the quadtree and octree algorithms are inefficient, because the subdivision process is isotropic (meaning in equal divisions in both the x- and y-directions for a computer representation of a two-dimensional object and in equal divisions in the x-, y-, and z-directions for a computer representation of a three-dimensional object). Both methods are limited in versatility. Of course, the computer representation typically is extremely anisotropic (meaning far from symmetric about the x-, y-, and z-axes).
Examples of prior art that teach or utilize the quadtree or octree division method include (i) Finnigan et al., U.S. Pat. No. 5,345,490, issued Sep. 6, 1994, entitled Method and Apparatus For Converting Computed Tomography (CT) Data Into Finite Element Models, and (ii) Meager, U.S. Pat. No. 4,694,404, issued Sep. 15, 1987, entitled High Speed Image Generation of Complex Solid Objects Using Octree Encoding.
A modification of the quadtree method is taught in Imao, et al., U.S. Pat. No. 4,944,023, issued Jul. 24, 1990, entitled Method of Describing Image Information. The method described in Imao, et al., however, is limited, as the quadtree and octree methods are, by requiring division of regions of the representation into equal subregions.
The present invention also differs from the division method described in M. Tamminen and H. Samet, Efficient Octree Conversion by Connectivity Labeling, 18 Computer Graphics 43 (July 1984). The article presents an algorithm for converting an octree or quadtree subdivision into a compact representation of the boundary of the object being analyzed. The division method described in the article divides computer representations into equal halves about a single axis, and cycles through a new axis at each level. The present invention is for constructing a compact representation of the entire volume, not just the boundary. Moreover, the present invention does not require performing the quadtree or the octree division method prior to application of the bitree division method. The present invention is more efficient and more versatile in that it does not require cycling to a new axis at each level.
Although the references cited above generally teach methods of dividing a computer representation, none of the references teach the bitree division method invention taught and claimed herein.
The two-dimensional bitree idea is described in M. Shpitalni, P. Bar-Yoseph and Y. Krimberg, "Finite Element Mesh Generation Via Switching Function Representation", 5 Finite Elements in Analysis and Design 119 (1989). However, the article does not describe implementation specifics such as controlling the level variation of adjacent subdivisions, known as "balancing" the subdivisions. Balanced subdivisions are often required for computer-aided design, computational physics and communications applications. Balancing the subdivisions in the context of the quadtree division method is discussed in D. Moore, "Cost of Balancing Generalized Quadtrees", Symposium on Solid Modeling and Applications-Proceedings 1995, 305-311 (ACM, New York 1995).
The three-dimensional bitree idea is not in the literature.
An article published in the IBM Technical Disclosure Bulletin, Vol. 37, No. 04A, April 1994, entitled Method for Geo-Referencing an Octree Data Structure, describes a method for tying an octree data structure to geographic coordinates.
An article published in the IBM Technical Disclosure Bulletin, Vol. 32, No. 8B, January 1990, entitled Two-Pass Antialiasing in Constructive Solid Geometry Rendering, describes a two step method utilizing the quadtree approach for antialiasing a picture. Neither article provides a technique for recursive and anisotropic division of a computer representation that is an alternative to and an improvement of the traditional quadtree or octree division method as is shown and claimed herein.